package leetcode_2301_2400;

public class LeeCode_2369 {
    public static void main(String[] args) {
        System.out.println(validPartition(new int[]{676575, 676575, 676575, 533985, 533985, 40495, 40495, 40495, 40495, 40495, 40495, 40495, 782020, 782021, 782022, 782023, 782024, 782025, 782026, 782027, 782028, 782029, 782030, 782031, 782032, 782033, 782034, 782035, 782036, 782037, 782038, 782039, 782040, 378070, 378070, 378070, 378071, 378072, 378073, 378074, 378075, 378076, 378077, 378078, 378079, 378080, 378081, 378082, 378083, 378084, 378085, 378086, 378087, 378088, 378089, 378090, 378091, 378092, 378093, 129959, 129959, 129959, 129959, 129959, 129959}));
    }
    private static boolean validPartition(int[] nums) {
        int n = nums.length;
        if (n == 2){
            return nums[1] == nums[0];
        }else if (n == 3){
            return (nums[2] == nums[1] && nums[1] == nums[0]) || (nums[1] == nums[0] + 1 && nums[2] == nums[1] + 1);
        }
        boolean[] dp = new boolean[n];
        if (nums[1] == nums[0]){
            dp[1] = true;
        }
        if ((nums[2] == nums[1] && nums[1] == nums[0]) || (nums[1] == nums[0] + 1 && nums[2] == nums[1] + 1)){
            dp[2] = true;
        }
        for (int i = 3; i < n; i++) {
            if (nums[i] == nums[i - 1]){
                dp[i] = dp[i - 2];
            }
            if (dp[i]){
                continue;
            }
            if ((nums[i] == nums[i - 1] && nums[i - 1] == nums[i - 2]) || (nums[i - 1] == nums[i - 2] + 1 && nums[i] == nums[i - 1] + 1)){
                dp[i] = dp[i - 3];
            }
        }
        return dp[n - 1];
    }
}
